/* 
 * This program gets a file containing single-line strings to form the
 * collection from where a given string will be searched for using one of the
 * two included sort algorithms with single or multi-threaded implementations. 
 * 
 * Compilation:
 *    cc -lm -pthread search.c -o search
 * 
 * Usage:
 *        search [-s][-a][-u][-h][-v][-n <nthreads>] <file> <algo> <string> 
 * 
 * where: <file> file to read. Each line must be a word to include in the collection.
 *        <algo> is the search algorithm to use ('sequential' or 'binary'. 'S' or 'B' are accepted).
 *        <string> is the string to search for.
 * 
 * options:
 * 
 *    -a            Show authors. Can only be used alone.
 *    -h            Show help. Can only be used alone.
 *    -n <nthreads> Number of threads to use. Doesn't override -s
 *    -s            Run the sequential (non-distributed) algorithm.
 *    -u            Display usage. Can only be used alone.
 *    -v            Verbose mode.
 * 
 * 
 * Authors:
 *          Danilo Riffo    - danriffo[at]gmail.com
 *          Christian Magro - cmagrop[at]gmail.com
 * 
 * 
 * 
 * 
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 * 
 */


#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>
#include  <pthread.h>
#include  <math.h>
#include  <sys/time.h>

/* Exit status definitions */
#define   SUCCESS 0;
#define   ERROR_INVALID_ARGS 1;
#define   ERROR_INVALID_ALGO 2;
#define   ERROR_INVALID_STRING 3;
#define   ERROR_PTHREAD 4;
#define   ERROR_INVALID_FILE 5;


/* Global variable definitions */
int   PARALLEL_FLAG = 1;        //1 for parallel, 0 for sequential. Default is parallel.
char  ALGORITHM_FLAG;           //'s' for sequential or 'b' for binary search algorithm.
char  *In_FILE = NULL;          //file to read strings from.
unsigned long int COL_SIZE;     //number of strings in the collection
unsigned char  *STRING;         //string to search into COLLECTION.
unsigned char  **COLLECTION;    //collection of strings to search into.
char  MSG[20];                  //message to show after searching.
int NTHREADS = 2;               //number of threads to work on. Default is 2.
int verbose = 0;                //verbose output flag. 0=silent 1=verbose.
int STOP_FLAG = 0;              //stops the binary search.

/* Method prototypes */
void display_usage();           //displays program usage information.
void display_help();            //displays program usage and help information.
void display_authors();         //displays program authors
void binary_single(unsigned long int *range);     //binary search, single-threaded.
void sequential_single(unsigned long int *range); //Sequential search, single-threaded.
void sequential_multi();                          //sequential search, multi-threaded (pthread).
void *seq_multi_thread(void *range);              //one thread of the multi-threaded sequential search.
void binary_multi();                              //binary search, multi-threaded (pthread).
void *bin_multi_thread(void *range);              //one thread of the multi-threaded binary search.
int  read_file();                                 //reads the collection from a file.



int main (int argc, char **argv){
  
  /***********       Argument parsing block.       ***********/
  int i;
  if (argc == 2){
    if (strcmp(argv[1], "-h") == 0 ){
        display_help();
    }else if (strcmp(argv[1], "-u") == 0 ){
        display_usage();
    }else if (strcmp(argv[1], "-a") == 0 ){
        display_authors();
    }else{
      printf("\nInvalid argument: '%s'\n", argv[1]);
      display_usage();
      return ERROR_INVALID_ARGS;
    }
    return SUCCESS;
  }else if (argc == 1){
    puts("\nNo arguments received.");
    display_usage();
    return ERROR_INVALID_ARGS;
  }else{
    for (i=1; i < argc - 3; i++){
      if (strcmp(argv[i], "-h") == 0 ){
          puts("\n-h parameter is not alone. Ignoring.");
      }else if (strcmp(argv[i], "-u") == 0 ){
          puts("\n-u parameter is not alone. Ignoring.");
      }else if (strcmp(argv[i], "-a") == 0 ){
          puts("\n-a parameter is not alone. Ignoring.");
      }else if (strcmp(argv[i], "-s") == 0 ){
          PARALLEL_FLAG = 0;
      }else if (strcmp(argv[i], "-v") == 0 ){
          verbose = 1;
      }else if (strcmp(argv[i], "-n") == 0 ){
          if (i == argc-4){
            puts("\nNot enough arguments.");
            display_usage();
          }else{
            i++;
            NTHREADS = atoi(argv[i]);  //set the number of threads to use.
          }
      }else{
          printf("\nUnrecognized option: '%s'\n", argv[i]);
          return ERROR_INVALID_ARGS;
      }
    }
    
    
    if (strcmp(argv[argc-2], "S") == 0 || strcmp(argv[argc-2], "sequential") == 0){
      ALGORITHM_FLAG = 's';
    }else if (strcmp(argv[argc-2], "B") == 0 || strcmp(argv[argc-2], "binary") == 0){
      ALGORITHM_FLAG = 'b';
    }else{
      puts("\nInvalid algorithm. Either use 'sequential', 'S', 'binary' or 'B'.");
      display_usage();
      return ERROR_INVALID_ALGO;
    }
    
    In_FILE = argv[argc-3];
    STRING = argv[argc-1];
    
  }
  
  
  
  /***********          Execution block.          ***********/
  if (!In_FILE){
    puts("No file given. Exiting.");
    return ERROR_INVALID_FILE;
  }else{
    int fread = read_file();
    if (fread){
      puts("Invalid file.");
      return ERROR_INVALID_FILE;
    }
  }
  
  /* set the default search result message to not found. */
  strcpy(MSG, "String not found.");
  
  struct timeval tv_start, tv_end, tv_diff;
  
  /* select the desired search method */
  unsigned long int range[2];
  if (ALGORITHM_FLAG == 's'){
    if (PARALLEL_FLAG == 1){
      gettimeofday(&tv_start, NULL); //begin measuring time
      sequential_multi();
      
    }else{
      range[0]=0;
      range[1]=COL_SIZE-1;
      gettimeofday(&tv_start, NULL); //begin measuring time
      sequential_single(range);
    }
  }else{
    if (PARALLEL_FLAG == 1){
      gettimeofday(&tv_start, NULL); //begin measuring time
      binary_multi();
      
    }else{
      range[0]=0;
      range[1]=COL_SIZE-1;
      gettimeofday(&tv_start, NULL); //begin measuring time
      binary_single(range);
    }
  }
  
  /* print the result message */
  printf("%s\n", MSG);
  
  
  gettimeofday(&tv_end, NULL); //finish measuring time
  timersub(&tv_end, &tv_start, &tv_diff);
  printf("Time elapsed: %ld.%06ld seconds.\n", tv_diff.tv_sec, tv_diff.tv_usec);
  
  
  return SUCCESS;
}


void display_help(){
  puts("This program gets a file containing single-line strings to form the");
  puts("collection from where a given string will be searched for using one of the");
  puts("two included sort algorithms with single or multi-threaded implementations.");
  
  display_usage();
  
  puts("\noptions:");
  
  puts(" ");
  puts("   -a            Show authors. Can only be used alone.");
  puts("   -h            Show help. Can only be used alone.");
  puts("   -n <nthreads> Number of threads to use. Doesn't override -s");
  puts("   -s            Run the sequential (non-distributed) algorithm.");
  puts("   -u            Display usage. Can only be used alone.");
  puts("   -v            Verbose mode.");
  puts("\n");
 
}

void display_usage(){
  puts("\nUsage:");
  puts("       search [-s][-a][-u][-h][-v][-n <nthreads>] <file> <algo> <string> \n");
  
  puts("where: <file> file to read. Each line must be a word to include in the collection.");
  puts("       <algo> is the search algorithm to use ('sequential' or 'binary'. 'S' or 'B' are accepted).");
  puts("       <string> is the string to search for.\n");
}

void display_authors(){
  puts("this program has been developed by:");
  
  puts("                                   Danilo Riffo    - danriffo[at]gmail.com");
  puts("                                   Christian Magro - cmagrop[at]gmail.com\n");
}

//range is a size 2 integer array containing the left and right boundaries
void binary_single(unsigned long int *range){
  
  if(STOP_FLAG)
    return; //stop searching if the string has already been found.
  
  if (range[0] <= range[1]){
    unsigned long int center = range[0] + (range[1] - range[0]) / 2;
    unsigned long int newrange[2];
    int comp = strcmp(COLLECTION[center], STRING);
    
    
    if (comp == 0){
      strcpy(MSG, "String found.");
      range[0] = range[1]+1;   //stop searching
      STOP_FLAG = 1;
      
    }else if (comp < 0 && range[0] < range[1]){
      newrange[0]=center+1;
      newrange[1]=range[1];
      binary_single(newrange);
      range[0] = range[1]+1;   //stop searching
      
    }else if (range[0] < range[1]){
      newrange[0]=range[0];
      newrange[1]=center-1;
      binary_single(newrange);
      range[0] = range[1]+1;   //stop searching
      
    }
  }
  
}

//range is a size 2 integer array containing the left and right boundaries
void sequential_single(unsigned long int *range){
  
  for (range[0]; range[0] <= range[1]; range[0]++){
    if (strcmp(COLLECTION[range[0]], STRING) == 0){
      strcpy(MSG, "String found.");
      range[0] = range[1]+1;   //stop searching
    }
  }
}

void sequential_multi(){
  
  pthread_t threads[NTHREADS];
  int i, t_check;
  unsigned long int t_size = roundl(COL_SIZE / NTHREADS);
  unsigned long int *range;
  
  range = (unsigned long int *) calloc(3, sizeof(unsigned long int));
  
  //create threads
  for (i=0; i<NTHREADS; i++){
    if (verbose == 1){
      printf ("Creating thread %d of %d\n", i+1, NTHREADS);
    }
    system("sleep 0.001"); //1 millisecond delay used to stabilize communication between threads
    range[0]=i;
    range[1]=i*t_size;
    range[2]=(i+1)*t_size-1;
    
    if (i == NTHREADS-1){
      range[2]=COL_SIZE-1;
    }
    
    t_check = pthread_create(&threads[i], NULL, seq_multi_thread, (void*) range);
    if (t_check){
      printf("ERROR code %d while creating thread %d\n", t_check, i+1);
    }
  }
  
  for (i=0; i<NTHREADS; i++){ //wait for all threads to complete
    t_check = pthread_join(threads[i], NULL);
    if (verbose == 1){
      printf ("Thread %d terminated.\n", i+1);
    }
  }
  
  if (verbose == 1)
    puts("All threads completed successfully.");
}

void *seq_multi_thread(void *t_number){
  
  unsigned long int *t_range = (unsigned long int *) t_number;
  int t_num = t_range[0];
  unsigned long int range[2];
  
  range[0]=t_range[1];
  range[1]=t_range[2];
  
  if (verbose == 1){
    printf ("Thread %d created with boundaries %ld and %ld\n\n", t_num+1, range[0], range[1]);
  }
  
  sequential_single(range);
  
  return NULL;
}

void binary_multi(){
  
  pthread_t threads[NTHREADS];
  int i, t_check;
  unsigned long int t_size = roundl(COL_SIZE / NTHREADS);
  unsigned long int *range;
  
  range = (unsigned long int *) calloc(3, sizeof(unsigned long int));
  
  //create threads
  for (i=0; i<NTHREADS; i++){
    if (verbose == 1){
      printf ("Creating thread %d of %d\n", i+1, NTHREADS);
    }
    system("sleep 0.001"); //1 millisecond delay used to stabilize communication between threads
    range[0]=i;
    range[1]=i*t_size;
    range[2]=(i+1)*t_size-1;
    
    if (i == NTHREADS-1){
      range[2]=COL_SIZE-1;
    }
    
    t_check = pthread_create(&threads[i], NULL, bin_multi_thread, (void*) range);
    if (t_check){
      printf("ERROR code %d while creating thread %d\n", t_check, i+1);
    }
  }
  
  for (i=0; i<NTHREADS; i++){ //wait for all threads to complete
    t_check = pthread_join(threads[i], NULL);
    if (verbose == 1){
      printf ("Thread %d terminated.\n", i+1);
    }
  }
  
  if (verbose == 1)
    puts("All threads completed successfully.");
}

void *bin_multi_thread(void *t_number){
  
  unsigned long int *t_range = (unsigned long int *) t_number;
  int t_num = t_range[0];
  unsigned long int range[2];
  
  range[0]=t_range[1];
  range[1]=t_range[2];
  
  if (verbose == 1){
    printf ("Thread %d created with boundaries %ld and %ld\n\n", t_num+1, range[0], range[1]);
  }
  
  binary_single(range);
  
  return NULL;
}

int read_file(){
  
  /* we assume the file contains ordered data. We're not sorting it. */
  FILE *InFile = fopen(In_FILE,"r");
  
  if (!InFile){
    return 1; //error
  }
  
  COL_SIZE = 0;
  unsigned char temp[80];
  
  while(fscanf(InFile, "%s", temp) != EOF){
    COL_SIZE++;
    COLLECTION = (unsigned char **) realloc(COLLECTION, COL_SIZE*sizeof(unsigned char *));
    COLLECTION[COL_SIZE-1] = (unsigned char *) calloc(strlen(temp)+1, sizeof(unsigned char));
    strcpy(COLLECTION[COL_SIZE-1],temp);
  }
  
  fclose(InFile);
  
  return 0;
}